#!/usr/bin/python

# reference to:
#  * http://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
#  * https://batchloaf.wordpress.com/2013/12/07/simple-dft-in-c/

import math

sample = []

def generate_input_data():
	out = []
	for i in range(0, 200):
		x = (math.pi/100)*i
		y = math.sin(x) + 0.5*math.cos(x)
		out.append(y)

	return out

def dft(time_zone_dat):
	n = len(time_zone_dat)
	print "length of input data: %d" %(n)

	outreal = []
	outimag = []
	for k in range(0, n):
		sumreal = 0
		sumimag = 0
		for t in range(0, n):
			angle = (2*math.pi*t*k)/n
			sumreal +=      time_zone_dat[t]*math.cos(angle)
			sumimag += (-1)*time_zone_dat[t]*math.sin(angle)
		outreal.append(sumreal)
		outimag.append(sumimag)

	return (outreal, outimag)


sample = generate_input_data()
freq_real,freq_imag = dft(sample)

for i in range(0, len(freq_real)):
	print "%d  %13.8f" %(i, freq_real[i])
